---
title: "2、卡片"
created: 2025-11-28
tags:
  - 算法
---

# 2、卡片

## 题目 [卡片](https://www.lanqiao.cn/paper/3829/problem/2383/)

![[image-fc3dc669.png]]

## 思路分析

![[image-f7af815d.png]]

一张卡片只有 11 一种分法 （1）

两张 11 12 22 三种 （1+2）

三张 11 12 13 22 23 33 六种 （1+2+3）

……（1+2+……+n)

所以呈现等差数列的性质

因为它说给的数据在1e9内 所以尽可能构造出到八位的所有项

给定一个n 要能分得出n个人 就必须大于等于n

所以在构造出的序列中 二分出 第一个大于n的数 下标就是需要的卡片数

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int a[N],s[N];

int main()

{

	int n;cin>>n;

	for(int i=1;i<10000;i++){

		a[i]=1+(i-1);

		s[i]=s[i-1]+a[i];

//		cout<<s[i]<<" ";

	}

	int l=1,r=10000;

	while(l<r){

		int m=l+r>>1;

		if(s[m]>=n)

			r=m;

		else

			l=m+1;

	}

	cout<<r;

	return 0;

}
```

傻逼了 只需要在构造的时候 看什么时候满足n就停止即可

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int a[N],s[N];

int main()

{

	int n;cin>>n;

	for(int i=1;;i++){

		a[i]=1+(i-1);

		s[i]=s[i-1]+a[i];

		if(s[i]>=n){

			cout<<i;

			return 0;

		}

	}

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[1、空间|1、空间]] 🏠 [[00-刷题理模型]] ➡️ [[3、直线|3、直线]]